package hot100.logos71To80;

import java.util.*;

/**
 * @author logos
 * date 2025/7/17 12:48
 * @version v1.0
 * @Package hot100.logos71To80
 */
public class logos75 {

    /**
     * 75. 前 K 个高频元素
     * https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int x : nums) {
                cnt.merge(x, 1, Integer::sum);
            }
            int maxCnt = Collections.max(cnt.values());
            List<Integer>[] buckets = new ArrayList[maxCnt + 1];
            Arrays.setAll(buckets, i -> new ArrayList<>());
            for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
                buckets[e.getValue()].add(e.getKey());
            }
            int[] ans = new int[k];
            int j = 0;
            for (int i = maxCnt; i >= 0 && j < k; i--) {
                for (int x : buckets[i]) {
                    ans[j++] = x;
                }
            }
            return ans;
        }
    }
}
